package main

import "fmt"

type point struct {
	x int
	y int
}

func nearestExit(maze [][]byte, entrance []int) int {
	m, n := len(maze), len(maze[0])
	x, y := entrance[0], entrance[1]
	stepMap := make(map[int]int)
	dirs := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	queue := []*point{}
	queue = append(queue, &point{x, y})
	stepMap[x*m+y] = 0
	for len(queue) > 0 {
		p := queue[0]
		queue = queue[1:]
		dx, dy := p.x, p.y
		step := stepMap[dx*m+dy]

		if (dx != x || dy != y) && (dx == 0 || dx == m-1 || dy == 0 || dy == n-1) {
			return step
		}

		for _, v := range dirs {
			nx, ny := dx+v[0], dy+v[1]

			if nx < 0 || nx >= m || ny < 0 || ny >= n || maze[nx][ny] == '+' {
				continue
			}
			keys := nx*m + ny
			if stepMap[keys] > 0 {
				continue
			}
			stepMap[keys] = step + 1
			queue = append(queue, &point{nx, ny})
		}
	}
	return -1
}

func main() {
	fmt.Println(nearestExit([][]byte{{'.'}, {'.'}, {'.'}, {'.'}}, []int{2, 0}))
	fmt.Println(nearestExit([][]byte{{'+', '.'}}, []int{1, 0}))
	fmt.Println(nearestExit([][]byte{{'.', '+'}}, []int{0, 0}))
	fmt.Println(nearestExit([][]byte{{'+', '+', '.', '+'}, {'.', '.', '.', '+'}, {'+', '+', '+', '.'}}, []int{1, 2}))
	fmt.Println(nearestExit([][]byte{{'+', '+', '+'}, {'.', '.', '.'}, {'+', '+', '+'}}, []int{1, 0}))
}
